package leetcode_day._2021._202103;

import java.util.HashMap;

/**
 * @author yzh
 * @data 2021/3/25 11:27
 * 删除排序链表中的重复元素 II
 * 思路：
 *   使用 hashmap 记录数字的个数
 */
public class _25_82 {
    public static void main(String[] args) {
        ListNode root = new ListNode(1, new ListNode(1,
                new ListNode(1, new ListNode(2, new ListNode(3)))));
        ListNode node = new _25_82().deleteDuplicates(root);
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
    }

    /**
     * 第一次遍历记录要删除的数字
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        HashMap<Integer, Object> map = new HashMap<>();
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) map.put(cur.val, 1);
            cur = cur.next;
        }
        ListNode ans = new ListNode();
        ans.next = head;
        cur = ans;
        while (cur.next != null) {
            if (map.containsKey(cur.next.val)) {
                cur.next = cur.next.next;
            } else cur = cur.next;
        }
        return ans.next;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
